#include <bits/stdc++.h>
using namespace std;

// #define ONLINE_JUDGE

#ifndef ONLINE_JUDGE
#define dbg(x...)                             \
	{                                         \
		cerr << "\033[32;1m" << #x << " -> "; \
		err(x);                               \
	}
void err()
{
	cerr << "\033[39;0m" << endl;
}
template <typename T, typename... A>
void err(T a, A... x)
{
	cerr << a << ' ';
	err(x...);
}
#else
#define dbg(...)
#endif

typedef long long LL;

const int N = 1e5 + 50;

int mu[N], prime[N], pcnt;
int minp[N];
void init()
{
	mu[1] = 1;
	for (int i = 2; i < N; ++i)
	{
		if (!minp[i])
		{
			minp[i] = i;
			mu[i] = -1;
			prime[pcnt++] = i;
		}
		for (int j = 0; j < pcnt; ++j)
		{
			LL nextp = 1LL * i * prime[j];
			if (nextp >= N)
				break;
			minp[nextp] = prime[j];
			if (i % prime[j] == 0)
			{
				mu[nextp] = 0;
				break;
			}
			else
			{
				mu[nextp] = -mu[i];
			}
		}
	}

	// for (int i = 1; i <= 20; ++i)
	// 	dbg(i, prime[i], mu[i]);
}

LL brutal(int a, int m)
{
	int g = __gcd(a, m);
	a /= g;
	m /= g;
	int ans = 0;
	for (int i = a; i < a + m; ++i)
		if (__gcd(i, m) == 1)
			++ans;
	return ans;
}

LL brutalf(int n, int m, int l, int r)
{
	LL res = 0;
	for (int i=l; i<=r; ++i)
	{
		res += mu[i] * (m / i);
	}
	return res;
}

LL brutal2(int a, int m)
{
	int g = __gcd(a, m);
	a /= g;
	m /= g;
	LL ans = brutalf(a+m-1, m, 1, m);
	return ans;
}

LL phi(LL x)
{
	LL ans = x, y = x;
	for (int i=0; i<pcnt; ++i)
	{
		if (y % prime[i] == 0)
		{
			ans = ans / prime[i] * (prime[i] - 1);
			while (y % prime[i] == 0)
				y /= prime[i];
		}
	}
	if (y > 1) ans = ans / y * (y-1);
	return ans;
}

int main(int argc, char const *argv[])
{
	init();
	int t;
	scanf("%d", &t);
	for (int kk = 0; kk < t; ++kk)
	{
		LL a, m;
		cin >> a >> m;
		LL g = __gcd(a, m);
		a /= g;
		m /= g;
		cout << phi(m) << endl;
	}
	return 0;
}